package hot150;

// https://leetcode.cn/problems/gas-station/?envType=study-plan-v2&envId=top-interview-150
public class q14 {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        return method1(gas, cost, gas.length);
    }

    /**
     *  暴力解法
     *  超出时间限制
     *  复杂度O(n^2)
     */
    public int method1(int[] gas, int[] cost, int n) {
        for (int i = 0 ; i < n ; i++) {
            int sum = 0;
            for (int j = i ; j < i + n ; j++) {
                int index = j % n;
                sum += gas[index] - cost[index];
                if (sum < 0) {
                    break;
                }
                if (j == i + n - 1) {
                    return i;
                }
            }
        }
        return -1;
    }


    /**
     *  贪心算法
     *  1 ms
     *  复杂度O(n)
     */
    public int method2(int[] gas, int[] cost, int n) {
        /*
         * 如果gas和大于cost和就一定能到达。
         * 找到欠最多油的index，然后下一个就是出发点。
         */
        int sum, index, mn;
        sum = index = mn = 0;
        for (int i = 0 ; i < n ; i++) {
            // 获取从头到尾的差值
            sum += gas[i] - cost[i];
            // 计算最小差值，如果最后的剩余值大于0，表示当前点可以覆盖前面的负值
            if (sum < mn) {
                index = i + 1;
                mn = sum;
            }
        }
        return sum < 0 ? -1 : index;
    }
}
